home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Cream of the Crop 1
/
Cream of the Crop 1.iso
/
PROGRAM
/
NTUMIN10.ARJ
/
LOGMIN_H.C
< prev
next >
Wrap
C/C++ Source or Header
|
1992-03-12
|
18KB
|
530 lines
/****************************************************************************
*
* Program name : LOGMIN_H.C
*
* Written By : Eng-Huat Ong and Kian-Mong Low.
*
* This is the actual minimization algorithm. Variation from the actual
* LOGMIN algorithm is as follows:
* 1. Minterms with adjacency 0 or 1 is minimised first
* 2. Select next minterm with lowest adjacency wrt b-array
* 3. If more than 1 such minterms, select one with the lowest
* adjacency wrt to a-array
* 4. To shrink the CPT, select an adjacent term, mi that has the
* largest wi AND is already covered
* 5. If more than one such adjacent terms are covered, select one
* with the lowest adjacency wrt to b-array
* 6. If more than one such adjacenct terms with lowest adjacency,
* select one that could cover most of the uncovered minterms
* if chosen to shrink away
* 7. If non of the adjacent term is covered (see step 4), select
* one with the lowest adjacency wrt b-array from the
* uncovered adj term at step 4.
*
* --------------------------------------------------------------------------
* Copyright (c) 1992. All Rights Reserved. Nanyang Technological
* University.
*
* You are free to use, copy and distribute this software and its
* documentation providing that:
*
* NO FEE IS CHARGED FOR USE, COPYING OR DISTRIBUTION.
*
* IT IS NOT MODIFIED IN ANY WAY.
*
* THE COPYRIGHT NOTICE APPEAR IN ALL COPIES.
*
* This program is provided "AS IS" without any warranty, expressed or
* implied, including but not limited to fitness for any particular
* purpose.
*
* If you find NTUMIN fast, easy, and useful, a note or comment would be
* appreciated. Please send to:
*
* Boon-Tiong Tan or Othman Bin Ahmad
* School of EEE
* Nanyang Technological University
* Nanyang Avenue
* Singapore 2263
* Republic of Singapore
*
***************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define mask8 255
unsigned char *logmin_h(a, b) /* pointer to a & b array passed */
unsigned char *a, *b;
{
unsigned short pterm, ma, mb, *pm, *pm1, *pm2, pos, pos1;
unsigned long m, k, count, count1, topow();
register long i, wo, wi;
register char j;
char test;
unsigned char adjacency();
unsigned char *c, *c1, *d, *e, *s, *temp, adj0, adji;
unsigned char n, adj, nspm, cover, countb, countc;
unsigned char *adjacent(), *reduce(), *cpt(), *ssm(), adj_of_mi();
mb = *(b+2)<<8 | *(b+1); /* no. of minterms in b-array */
n = *a; /* no. of variables */
nspm = *(a+3); /* no. of bytes/minterm */
ma = *(a+2)<<8 | *(a+1); /* no. of minterms in a-array */
temp = (unsigned char *) malloc(nspm+1); /* temporary storage */
if (temp == 0)
{
printf("Out of memory -- LOGMIN_H, *temp\n");
printf("Program terminated - 1\n");
exit(0);
}
s = (unsigned char *) malloc(4); /* header of s-array */
if (s == 0)
{
printf("Out of memory -- LOGMIN_H, *s\n");
printf("Program terminated - 2\n");
exit(0);
}
pterm = 0; /* no. of product term */
/***
*** MINIMIZE ALL MINTERMS WITH ADJACENCY OF 0 & 1 FIRST
***/
for (i=0; i<mb; i++) /* for adj = 0 or 1 */
{
*b = n; /* assign back to n */
memcpy(temp, (b+4+nspm*i), nspm); /* pick a minterm from b-array */
c = adjacent(temp, a, 1); /* obtain the adjacent terms */
adj = *(c+1); /* adjacency of minterm */
if (adj <= 1) /* adjacency 0 or 1 */
{
d = cpt(c); /* generate CPT */
s = (unsigned char *) realloc(s,4+n*(pterm+1)); /* more space */
if (s == 0)
{
printf("Out of memory -- LOGMIN_H, *s\n");
printf("Program terminated - 3\n");
exit(0);
}
memcpy ((s+4+n*pterm),d,n); /* add CPT to soln array */
pterm++; /* product term count */
b = reduce(c,b,i); /* remove minterms covered from b-array */
i = (char) *b; /* index pointer of b-array */
mb = *(b+2)<<8 | *(b+1); /* value of mb altered in b-array */
free(d); /* free pointer */
}
free(c); /* free pointer */
}
/***
*** MINIMIZE MINTERMS WITH ADJACENCY GREATER THAN 1
***/
while (mb > 0)
{
adj0 = 255; /* max for 8-bit */
*b = n; /* assign back to n */
/***
*** OBTAIN AN ARRAY, PM OF POSITION OF ADJACENT TERMS WITH THE LOWEST
*** ADJACENCY WRT B-ARRAY
***/
for (i=0; i<mb; i++)
{
memcpy(temp, (b+4+nspm*i), nspm); /* pick a minterm */
adji = adjacency(temp, b); /* adj wrt b-array */
if (adji<adj0) /* look for lowest adj */
{
if (adj0!=255) /* not the 1st term */
free(pm);
adj0 = adji; /* update lowest adj */
count = 1; /* set count to 1 */
pm = (unsigned short *) malloc(2); /* space for pos */
if (pm == 0)
{
printf("Out of memory -- LOGMIN_H, *pm\n");
printf("Program terminated - 4\n");
exit(0);
}
*pm = i; /* 1st pos of minterm */
}
else if (adji==adj0) /* adjacency as low */
{
count++; /* no. of elements in pm-array */
pm = (unsigned short*) realloc(pm, 2*count); /* more space */
if (pm == 0)
{
printf("Out of memory -- LOGMIN_H, *pm\n");
printf("Program terminated - 5\n");
exit(0);
}
*(pm+count-1) = i; /* elements in pm-array */
}
}
if (count==1) /* if only 1 element in pm-array */
pos = *pm;
else
{
/***
*** FORM PM-ARRAY, SELECT THE 1ST ADJACENT TERM THAT HAS THE
*** LOWEST ADJACENCY WRT A-ARRAY
***/
adj0 = 255; /* max for 8-bit */
for (i=0; i<count; i++) /* do for all in pm-array */
{
memcpy(temp, (b+4+nspm*(*(pm+i))), nspm);
adji = adjacency(temp, a); /* adj wrt a-array */
if (adji<adj0) /* new lowest found */
{
adj0 = adji; /* update lowest */
pos = *(pm+i); /* position of required minterm */
}
}
}
free(pm);
memcpy(temp, (b+4+nspm*pos), nspm); /* pick the required minterm */
/***
*** GENERATE SSM AND TEST FOR COVERAGE BY FUNCTION
***/
c = adjacent(temp, a, 255); /* obtain adjacent terms */
adj = *(c+1); /* adjacency of minterms */
d = cpt(c); /* generate CPT */
e = ssm(d); /* generate SSM */
m = topow(*(e+1)); /* no. of SSM terms */
for (j=0; j<m; j++) /* check for SSM coverage */
{
memcpy (temp, (e+4+nspm*j), nspm);
test = exist (temp, a, ma);
if (test == -1) /* SSM term not in a-array */
break;
}
/***
*** ALL SSM COVERED BY THE FUNCTION, SELECT CPT AS PRODUCT TERM
***/
if (test == 0) /* all SSM's covered by fn */
{
if (m > 65536) /* too many SSM terms */
{
printf("Product Term Too Huge \n");
printf("Program terminated \n");
exit(0);
}
*(e+1) = (m-1) & mask8; /* no. of SSM terms minus 1 */
*(e+2) = (m-1)>>8 & mask8;
b = reduce(e,b,i); /* reduce minterms covered from b-array */
mb = *(b+2)<<8 | *(b+1); /* no. of minterms in b-array */
s = (unsigned char *) realloc(s, 4+n*(pterm+1)); /* more space */
if (s == 0)
{
printf("Out of memory -- LOGMIN_H, *s\n");
printf("Program terminated - 6\n");
exit(0);
}
memcpy((s+4+n*pterm),d,n); /* add CPT to soln array */
pterm++; /* no. of product terms */
free(d); /* free pointers */
free(e);
}
else
{
/***
*** SSM NOT COVERED BY THE FUNCTION
***/
free(d); /* free pointer */
cover =0; /* coverage status */
while (!cover) /* do until shrinked SSM is covered */
{
/***
*** OBTAIN AN ARRAY, PM OF POSITIONS OF ADJACENT TERMS, MI WITH THE LARGEST WI
***/
wo = -1; /* initial value */
for (j=0; j<adj; j++) /* do for all adjacent terms */
{
memcpy(temp,(c+4+nspm*(j+1)),nspm); /* pick adjacent term */
wi = adj_of_mi(temp,e,a); /* obtain wi */
if (wi>wo)
{
if (wo != -1) /* not the first */
free(pm);
wo = wi; /* new lowest value */
count = 1; /* reset count to 1 */
pm = (unsigned short *) malloc(2); /* space for pm */
if (pm==0)
{
printf("Out of memory -- LOGMIN_H, *pm\n");
printf("Program terminated - 7\n");
exit(0);
}
*pm = j; /* first element */
}
else if (wi==wo) /* wi as large */
{
count++; /* no. of element in pm-array */
pm = (unsigned short *) realloc (pm, 2*count); /* more space */
if (pm==0)
{
printf("Out of memory -- LOGMIN_H, *pm\n");
printf("Program terminated - 8\n");
exit(0);
}
*(pm+count-1) = j; /* elements of pm-array */
}
}
free(e); /* free pointer */
/***
*** DETERMINE FROM PM-ARRAY, AN ARRAY, PM1 OF POSITION OF ADJACENT TERMS
*** THAT HAVE ALREADY BEEN COVERED
***/
pm1 = (unsigned short *) malloc(2); /* space for pm1 */
if (pm1==0)
{
printf("Out of memory -- LOGMIN_H, *pm1\n");
printf("Program terminated - 9\n");
exit(0);
}
k = 0;
for (j=0; j<count; j++) /* do for all element in pm-array */
{
memcpy(temp, (c+4+nspm*(1+ *(pm+j))), nspm); /* pick adj term */
test = exist(temp,b,mb);
if (test == -1) /* already covered */
{
memcpy((pm1+k++), (pm+j), 2); /* transfer pos to pm1 */
pm1 = (unsigned short *) realloc(pm1, 2*(k+1)); /* more space */
if (pm1==0)
{
printf("Out of memory -- LOGMIN_H, *pm1\n");
printf("Program terminated - 10\n");
exit(0);
}
}
}
/***
*** OBTAIN FROM PM1-ARRAY, AN ARRAY PM2 OF ADJACENT TERMS, MI WITH
*** THE LOWEST ADJACENCY WRT B-ARRAY
***/
if (k != 0) /* some elements in pm1 */
{
pm2 = (unsigned short *) malloc(2*k); /* space for pm2 */
if (pm2==0)
{
printf("Out of memory -- LOGMIN_H, *pm2\n");
printf("Program terminated - 11\n");
exit(0);
}
adj0 = 255; /* max of 8-bit */
for (j=0; j<k; j++) /* all elements in pm1-array */
{
memcpy(temp, (c+4+nspm*(1+*(pm1+j))),nspm); /* pick adj term */
adji = adjacency(temp,b); /* adj wrt b-array */
if (adji<adj0) /* new lowest adj */
{
count1 = 1; /* no. in pm2-array */
adj0 = adji; /* update lowest */
*pm2 = *(pm1+j); /* element in pm2 */
}
else if (adji==adj0) /* adj as small */
{
count1++; /* no. in pm2-array */
*(pm2+count1-1) = *(pm1+j); /* element in pm2 */
}
}
free(pm1); /* free pointer */
if (count1 == 1) /* only 1 element in pm2-array */
pos = *pm2; /* position of required adj term */
else
{
/***
*** SHRINK CPT, TAKING EACH OF THE CORRESPONDING ADJACENT
*** TERMS IN PM2-ARRAY AND TAKE THE ONE WHOSE SHRINKED CPT
*** COVERS MOST OF THE TERMS IN B-ARRAY
***/
countc = 0; /* lowest value */
c1 = (unsigned char *) malloc(4+(*(c+1)+1)*nspm); /* space for adj terms */
if (c1==0)
{
printf("Out of memory -- LOGMIN_H, *c1\n");
printf("Program terminated - 12\n");
exit(0);
}
for (j=0; j<count1; j++) /* all elements in pm2-array */
{
memcpy(c1, c, 4+nspm*(1+ *(c+1))); /* pick adj term */
*(c1+1) = *(c+1)-1; /* decrement adjacency */
pos1 = *(pm2+j); /* adj term to shrink in turn */
memcpy ((c1+4+nspm*(1+pos1)), (c1+4+nspm*(2+pos1)), nspm*(*(c1+1)-pos1));
d = cpt(c1); /* generate shrinked CPT */
e = ssm(d); /* generate shrinked SSM */
m = topow (*(e+1)); /* no. of SSM terms */
countb = 0; /* reset counter */
for (i=0; i<m; i++) /* do for all SSM's in e-array */
{
memcpy(temp, (e+4+nspm*i), nspm); /* pick SSM term */
test = exist(temp, b, mb);
if (test==0) /* still in b-array */
countb++; /* coverage count */
}
if (countb>=countc) /* largest count found */
{
countc = countb; /* update largest count */
pos = pos1; /* required pos of adj term */
}
free(d); /* free pointers */
free(e);
}
free(c1); /* free pointer */
}
free(pm2); /* free pointer */
}
else /* non in pm1-array */
{
/***
*** ALL TERMS IN PM-ARRAY HAS NOT BEEN COVERED, SELECT ONE
*** WITH THE LOWEST ADJACENCY WRT B-ARRAY
***/
adj0 = 255; /* max for 8-bit */
for (j=0; j<count; j++) /* all in pm-aaray */
{
memcpy(temp, (c+4+nspm*(1+ *(pm+j))), nspm); /* pick adj term */
adji = adjacency(temp, b); /* adj wrt b-array */
if (adji<adj0) /* lowest adj found */
{
adj0 = adji; /* update lowest */
pos = *(pm+j); /* required position of adj term */
}
}
}
free(pm); /* free pointer */
adj--; /* no. of adj term after shrinking */
*(c+1) = adj; /* adjacency after shrinking */
/***
*** SHRINK CPT (REMOVE THE SELECTED ADJACENT TERM FROM C-ARRAY),
*** GENERATE NEW CPT, SSM AND TEST FOR COVERAGE BY FUNCTION
***/
memcpy((c+4+nspm*(1+pos)), (c+4+nspm*(2+pos)), nspm*(adj-pos)); /* shrink CPT */
c = (unsigned char*) realloc(c, 4+nspm*(1+adj)); /* reduce space */
if (c==0)
{
printf("Out of memory -- LOGMIN_H, *c\n");
printf("Program terminated - 13\n");
exit(0);
}
d = cpt(c); /* generate CPT */
e = ssm(d); /* generate SSM */
m = topow(*(e+1)); /* no. of SSM terms */
for (i=0; i<m; i++) /* check SSM coverage by function */
{
memcpy(temp, (e+4+nspm*i), nspm); /* pick SSM term */
test = exist(temp,a,ma);
if (test == -1) /* SSM term not covered */
break;
}
/***
*** SHRINKED SSM COVERED BY FUNCTION, REDUCE B-ARRAY
*** AND SELECT SHRINKED CPT AS PRODUCT TERM
***/
if (test==0) /* SSM covered */
{
if (m > 65536) /* too many SSM terms */
{
printf("Product Term Too Huge \n");
printf("Program terminated \n");
exit(0);
}
*(e+1) = (m-1) & mask8; /* no. of SSM terms minus 1 */
*(e+2) = (m-1)>>8 & mask8;
b = reduce(e, b, i); /* remove minterms covered from b-array */
mb = *(b+2)<<8 | *(b+1); /* no. of minterms in b-array */
s = (unsigned char *) realloc(s, 4+n*(pterm+1)); /* more space */
if (s==0)
{
printf("Out of memory -- LOGMIN_H, *s\n");
printf("Program terminated - 14\n");
exit(0);
}
memcpy ((s+4+n*pterm), d, n); /* add shrinked CPT to soln array */
pterm++; /* no. of product terms */
cover = 1; /* coverage status */
free(e); /* free pointer */
}
free (d); /* free pointer */
}
}
free(c); /* free pointer */
}
*s = n; /* no. of variables */
*(s+1) = pterm & mask8; /* no. of product terms in 2 bytes */
*(s+2) = pterm>>8 & mask8;
free(temp); /* free pointer */
free(a);
free(b);
return(s); /* return solution array */
}
